
public class Solution {
	
	public static void main(String[] argv){
		ListNode a = new ListNode(3);
		ListNode b = new ListNode(2);
		ListNode c = new ListNode(4);
		a.next = b;
		b.next = c;
		
		Solution s = new Solution();
		s.insertionSortList(a);
		
	}
	
	public ListNode insertionSortList(ListNode head) {

		ListNode finalHead = head;

		ListNode parentNode = head;

		if (head == null || head.next == null)
			return head;
		else
			head = head.next;

		while (head != null) {

			// Get next node
			ListNode currentNode = new ListNode(head.val);
			ListNode start = finalHead;
			ListNode startParent = null;

			while (true) {

				if (start == currentNode)
					break;

				if (currentNode.val <= start.val) {
					// Re-arrange nodes

					if (startParent == null) {
						currentNode.next = start;
						finalHead = currentNode;

						parentNode.next = head.next;
					} else {
						startParent.next = currentNode;
						currentNode.next = start;

						parentNode.next = head.next;
					}
					break;
				}

				startParent = start;
				start = start.next;
			}
			parentNode = head;
			head = head.next;
		}
		return finalHead;
	}
}